/**
 * 求最大子段和，允许删掉一个元素（不删也行）
 * 
 * 不删的话，仍然是原来的最大子段和，现在考虑删除情况下的
 * 
 * 令Ui仍然是以i结尾的且选i的最大子段和
 * 令 Xi 为以i结尾的选i且包含删除的最大子段和
 * 则 Xi = Ai + max(U[i-2], X[i-1])
 * 
 * 其中前者表示删除的就是i-1，后者表示删除位置还在i-1之前
 * 求出X[N]，再与正常子段和答案对比一下即可
 */
class Solution {

using vi = vector<int>;

int N;
vi D, U, X;

public:
    int maximumSum(vector<int>& arr) {
        N = arr.size();
        arr.insert(arr.begin(), 0);
        D.assign(N + 1, 0);
        U.assign(N + 1, 0);
        X.assign(N + 1, 0);

        U[1] = arr[1];
        X[1] = arr[1];
        D[1] = arr[1];
        for(int i=2;i<=N;++i){
            U[i] = max(U[i - 1] + arr[i], arr[i]);
            X[i] = max(arr[i] + X[i - 1], arr[i] + U[i - 2]);
            D[i] = D[i - 1];
            chkmax(D[i], U[i]);
            chkmax(D[i], X[i]);
        }        
        return D[N];
    }
    void chkmax(int & d, int a){
        if(d < a) d = a;
    }
};
